open Geo;;

	type arbre = Feuille of segment list | Noeud of arbre*segment list*arbre
	
(*---------------------------------------------------------------------------------*)
(* True -> b est a droite de a *)
	let (droite: segment -> segment -> bool) = fun a b->
		if not (seCroisent a b ) then
			let vb = (if( b.p1.y >= b.p2.y) then {(b.p1.x -. b.p2.x);(b.p1.y -. b.p2.y)}else {(b.p2.x -. b.p1.x);(b.p2.y -. b.p1.y)} in
			let va = (if( a.p1.y >= a.p2.y) then {(a.p1.x -. a.p2.x);(a.p1.y -. a.p2.y)}else {(a.p2.x -. a.p1.x);(a.p2.y -. a.p1.y)} in
			let angle = acos(dot (unitise vb) (unitise va)) in
			let angleR = 90 - angle in
			
		else
			failwith "les segments ce croisent"

(*---------------------------------------------------------------------------------*)
	let (part_int: segment -> segment list -> segment list*segment list*segment list) = fun c l ->
		let rec (aux: segment -> segment list -> segment list -> segment list -> segment list*segment list*segment list) = fun c lg ls ld ->
			match l with
				| a::[] -> 
					if (seCroisent c a) then
						(lg,a::ls,ld)
					else if (droite c a) then
						(lg,ls,a::ld)
					else
						(a::lg,ls,ld)
				| h::t ->
					if (seCroisent c h) then
						aux lg (h::ls) ld
					else if (droite c h) then
						aux lg ls (a::ld)
					else
						aux (a::lg) ls ld
						
(*---------------------------------------------------------------------------------*)
	let (partition: segment -> segment list -> segment list*segment list) = fun c l ->
		let (l1,l2,l3) = part_int l in
		let rec (aux: segment -> segment list -> segment list -> segment list -> segment list*segment list) = fun c lg ls ld ->
			match ls with 
				| a::[] -> 
					let pi = pointCommun c a in
					let a1 = {p1=a.p1;p2=pi} in
					let a2 = {p1=pi;p2=a.p2} in
					if (droite a1 c) then
						(a2::lg,a1::ld)
					else
						(a1::lg,a2::ld)
				| h::t ->
					let pi = pointCommun c h in
					let a1 = {p1=h.p1;p2=pi} in
					let a2 = {p1=pi;p2=h.p2} in
					if (droite a1 c) then
						aux c (a2::lg) t (a1::ld)
					else
						aux c (a1::lg) t (a2::ld)
		
(*---------------------------------------------------------------------------------*)	
	let (createBSP: segment list -> arbre) = fun l ->
		let rec (aux: segment list -> arbre) = fun li->
			match li with
				[] -> Feuille([])
				| h::[] -> Feuille([h])
				| h::t ->
					let pivot = h in
					(* Il faut modifier PIVOT pour le faire sortir de la maison*)
					let (lg,ld) = partition pivot li in
						Noeud(aux lg,li,aux ld)
		in
		aux l
	
